package 动态规划;

public class LeetCode673_最长递增子序列个数 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        int[] dp = new int[n]; // 最大递增子序列长度
        int[] cnt = new int[n]; // 最大递增子序列个数
        for (int i = 0; i < n; ++i) { // 初始化
            dp[i] = 1;  // 长度为 1
            cnt[i] = 1; // 个数为 1
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) { // 当第i个数大于第j个数时
                    if (dp[j] + 1 > dp[i]) {
                        // 当第j个数的最大递增子序列长度+1 大于 当前第i数的最大长度
                        dp[i] = dp[j] + 1;// 更新第i数的最大长度
                        cnt[i] = cnt[j]; // 更新第i数的最大长度个数
                    } else if (dp[j] + 1 == dp[i]) {
                        // 当第j数的最大递增子序列长度+1 等于 当前第i数的最大长度
                        cnt[i] += cnt[j]; // 就累加个数
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }

}
